//实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 
//
// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 
//
// 必须原地修改，只允许使用额外常数空间。 
//
// 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 
//1,2,3 → 1,3,2 
//3,2,1 → 1,2,3 
//1,1,5 → 1,5,1 
// Related Topics 数组 
// 👍 621 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//Java：下一个排列
public class P31NextPermutation {

    /**
     *
     * 思路： 将最后一位 移到前面第一个比他小的数字的前面，然后剩下的排序       8 1 7 6 5 4 3 改成 8 3 1 4 5 6 7
     *      然后再循环一次 判断倒二，倒三位
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 99.77% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 51.32% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 将最后一位 移到前面第一个比他小的数字的前面，然后剩下的排序       8 1 7 6 5 4 3 改成 8 3 1 4 5 6 7
        public void nextPermutation(int[] nums) {
            int length = nums.length;
            if (nums.length == 0 || nums.length == 1) {
                return;
            }
            for (int i = 0; i < length - 1; i++) {
                if (nums[i] < nums[i + 1]) {
                    break;
                }
                if (i == length - 2) {
                    Arrays.sort(nums);
                    return;
                }
            }

            // 1 5 1
            int tempIndex = -1;
            int tempIndex2 = -1;

            // 一开始只有一层循环 是 将最后一位 移到前面第一个比他小的数字的前面，结果在 [2,3,0,2,4,1] 的结果中，输出是 [2,3,1,0,2,4]，然而答案是 [2,3,0,4,1,2]
            // 所以最外层还得判断 i 是否是最大的值，不是的话，得从last -- ，从倒二个开始再比较
            for (int last = length - 1; last > tempIndex; last--) {
                for (int i = last - 1; i >= 0; i--) {
                    // 此处再加一个last循环
                    if (nums[i] < nums[last]) {
                        if (i > tempIndex) {
                            tempIndex2 = last;
                            tempIndex = i;
                            continue;
                        }

                        break;
                    } else if (nums[i] == nums[last]) {
                        break;
                    }
                }
            }
            exchange(nums, tempIndex, tempIndex2);
            // 排序 tempIndex+1, length-1 的数据
            sort(nums, tempIndex + 1, nums.length - 1);
        }

        // 交换两数
        private void exchange(int[] nums, int i, int k) {
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }

        // 排序下标 start到end 的数据
        // 直接选择
        private void sort(int[] nums, int start, int end) {
            if (start >= end) {
                return;
            }
            for (int i = start; i < end + 1; i++) {
                int min = i;
                for (int k = i + 1; k < end + 1; k++) {
                    if (nums[k] < nums[min]) {
                        min = k;
                    }
                }
                exchange(nums, i, min);
            }
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P31NextPermutation().new Solution();
        int[] nums = new int[]{1,2,5};
        solution.nextPermutation(nums);
        for (int a : nums) {
            System.out.print(a + " ");
        }
        // TO TEST
    }

}